Carmichael の定理
$ ^{\forall a\in(\Z/n\Z)}[a^m\overset n\equiv1] を満たす最小の$ m=\lambda(n)を求める定理
Euler の定理より$ m=\varphi(n)とすれば式を満たすが、コレは最小とは限らない ただし、$ nと互いに素な$ aが与えられた時に$ a^m\overset n\equiv1を満たす最小の$ mは$ \lambda(n)となるとは限らない 1. $ n=2^eのとき
$ \lambda(2^e)=\begin{cases}1&(e=1)\\2&(e=2)\\2^{e-2}&(e\ge3)\end{cases}
2. $ n=p^eのとき ($ pは奇素数)
$ \lambda(p^e)=p^{e-1}(p-1)
3. $ n=\prod_{i=1}^{k>2}p_i^{e_i}と素因数分解できるなら $ \lambda(\prod_{i=1}^{k\ge2}p_i^{e_i})={\rm lcm}_{i=1}^{k>2}\{\lambda(p_i^{e_i})\}
$ a^{\lambda(n)}\overset n\equiv1
$ \lambda(n)が$ n-1の約数なので$ a^{n-1}\overset n\equiv1となって、Fermat 素数判定法に通ってしまう $ n=\prod_{i=1}^kp_i^{e_i}と素因数分解するとき (上と違って$ k\ge1に注意)
$ (\Z/n\Z)^\times\simeq(\Z/p_1^{e_1}\Z)^\times\times\cdots\times (\Z/p_k^{e_k}\Z)^\timesが成立
$ ^\timesは$ ^*と同様に乗法逆元の存在を示す 各場合を分けて考える
$ n=2^eの時
$ (\Z/2^e\Z)^\times\simeq\begin{cases}\{e\}&(e=1)\\\Z/2\Z&(e=2)\\\Z/2\Z\times\Z/2^{e-2}\Z&(e\ge3)\end{cases}
なんで？Summer498.icon
$ n=p^e\quad(p\ge3)のとき
$ (\Z/p^e\Z)^\times\simeq\Z/(p^{e-1}(p-1))\Z
なんで？Summer498.icon
$ ^\timesが抜けてるみたいな間違いをしてそう